# Definition for a binary tree node.
import collections


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        # 递归版
        if not root:
            return 0
        left_count = self.maxDepth(root.left) +1
        right_count = self.maxDepth(root.right) +1
        return max(left_count,right_count)


#         非递归
#         if not root:
#             return 0
#         else:
#             res = 1
#             queue= collections.deque()
#             queue.append((root,1))
#             while queue:
#                 node,count = queue.popleft()
#                 if node.left:
#                     queue.append((node.left,count+1))
#                 if node.right:
#                     queue.append((node.right,count+1))
#                 res = max(res,count)
#         return res








m1 = TreeNode(1)
m1.left = TreeNode(2)
m1.right = TreeNode(3)
m1.right.right = TreeNode(3)
# m1.right.right.right = TreeNode(3)
# m1.right.right.right.right= TreeNode(3)

s = Solution()

t = s.maxDepth(m1)
print(t)
